package hotLeetcode;

import java.util.PriorityQueue;

public class H23Leetcode {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 如果只有一个链表，直接返回
        if (lists.length == 1) {
            return lists[0];
        }

        // 对于两个链表的情况，直接使用 mergeTwo 方法
        if (lists.length == 2) {
            return mergeTwo(lists[0], lists[1]);
        }
        ListNode merged = lists[0];
        for (int i = 1; i < lists.length; i++) {
            merged = mergeTwo(merged, lists[i]);

        }


        return merged;
    }

    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        ListNode p = new ListNode(-1, null);
        ListNode s = p;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                s.next = l1;
                l1 = l1.next;
            } else if (l1.val > l2.val) {
                s.next = l2;
                l2 = l2.next;
            } else {
                s.next = l1;
                l1 = l1.next;
            }

            s = s.next;


        }

        if (l1 == null) {
            s.next = l2;
        }
        if (l2 == null) {
            s.next = l1;
        }

        return p.next;

    }

    PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
        return o1.val - o2.val;
    });

    public ListNode mergeKLists2(ListNode[] lists) {
        //创建一个优先队列


        //先把头节点放入
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }

        ListNode dummy = new ListNode(-1, null);
        ListNode s = dummy;
        while (!pq.isEmpty()) {
            ListNode poll = pq.poll();
            s.next = poll;
            poll = poll.next;
            s = s.next;
            if (poll != null) {
                pq.offer(poll);
            }
        }


        return dummy.next;
    }



}
